10108. Tree Одинаковые

Заданы два бинарных дерева. Проверьте, одинаковы ли они. Два бинарных дерева считаются одинаковыми, если по структуре они идентичны, а соответствующие вершины содержат одинаковые значения.

Определение дерева:

//Java

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

left = null;

right = null;

}

}

// C++

class TreeNode

{

public:

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

Реализуйте функцию isSame, которая  возвращает true если деревья одинаковые и false иначе.

// Java

boolean isSame(TreeNode tree1, TreeNode tree2)

// C++

bool isSame(TreeNode *tree1, TreeNode *tree2)

Пример

Функция isSame возвращает true, так как деревья одинаковые.

РЕШЕНИЕ

дерево

Анализ алгоритма

Если tree₁ = tree₂ = NULL, то деревья идентичны.

Если один из указателей tree₁ или tree₂ равен NULL, а второй не равен NULL, то деревья не идентичны.

Если tree₁ → val и tree₂ → val не равны между собой, то деревья не идентичны.

Если tree₁ → val и tree₂ → val равны, то рекурсивно проверяем идентичность их левых и правых поддеревьев.

Реализация алгоритма

bool isSame(TreeNode *tree1, TreeNode *tree2)

{

Если tree1 = tree2 = NULL, то деревья идентичны.

if (tree1 == NULL && tree2 == NULL)

return true;

Если один из указателей tree₁ или tree₂ равен NULL, а второй не равен NULL, то деревья не идентичны.

else if (tree1 == NULL || tree2 == NULL)

return false;

if (tree1->val == tree2->val)

{

Если tree₁ → val и tree₂ → val равны, то рекурсивно проверяем идентичность их левых и правых поддеревьев.

bool left = isSame(tree1->left, tree2->left);

bool right = isSame(tree1->right, tree2->right);

return left && right;

}

Если tree₁ → val и tree₂ → val не равны между собой, то деревья не идентичны.

return false;

}

Java реализация

boolean isSame(TreeNode tree1, TreeNode tree2)

{

if (tree1 == null && tree2 == null)

return true;

else if (tree1 == null || tree2 == null)

return false;

if (tree1.val == tree2.val)

{

boolean left = isSame(tree1.left, tree2.left);

boolean right = isSame(tree1.right,tree2.right);

return left && right;

}

return false;

}